package com.hanxiaozhang.recursion.violentrecursion;

/**
 * 〈一句话功能简述〉<br>
 * 〈给定两个长度都为N的数组weights和values，
 *  weights[i]和values[i]分别代表i号物品的重量和价值。
 *  给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。
 *  返回你能装下最多的价值是多少? 〉
 *
 * @author hanxinghua
 * @create 2021/10/13
 * @since 1.0.0
 */
public class Knapsack {


    public static void main(String[] args) {
        int[] weights = {3, 2, 4, 7};
        int[] values = {5, 6, 3, 19};
        int bag = 11;
        System.out.println(getMaxValue(weights, values, bag));
        System.out.println(maxValue(weights, values, bag));
        System.out.println(dpWay(weights, values, bag));
    }

    /**
     * 实现方式1
     *
     * @param w
     * @param v
     * @param bag
     * @return
     */
    public static int getMaxValue(int[] w, int[] v, int bag) {
        return process(w, v, 0, 0, bag);
    }


    /**
     * 递归：
     * 递归目的返回 index...（index之后）最大价值
     *
     * @param w        物品的重量数组
     * @param v        物品的价值数组
     * @param index    处理位置
     * @param alreadyW 0 ~ index-1 上做了货物的选择，使得你已经达到的重量的多少
     * @param bag      背包总载重
     * @return 返回 -1 说明没有这种方案，不返回-1，返回的值是真实的值
     */
    public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
        // 超重，返回 -1
        if (alreadyW > bag) {
            return -1;
        }
        // 重量没超，并且index==w.length，数组越界，没有货了，返回0
        if (index == w.length) {
            return 0;
        }
        // 可能性1（p1）：没有要当前位置的货，接下来货可能产生的价值
        int p1 = process(w, v, index + 1, alreadyW, bag);
        // 要当前位置的货，接下来货可能产生的价值
        int p2next = process(w, v, index + 1, alreadyW + w[index], bag);
        // 可能性2（p2）
        int p2 = -1;
        if (p2next != -1) {
            p2 = v[index] + p2next;
        }
        // 求最大值
        return Math.max(p1, p2);
    }


    /**
     * 实现方式2
     *
     * @param w
     * @param v
     * @param bag
     * @return
     */
    public static int maxValue(int[] w, int[] v, int bag) {
        return process(w, v, 0, bag);
    }


    /**
     * 只剩下rest的空间了，
     * index...(之后)货物自由选择，但是不要超过rest的空间
     * 返回能够获得的最大价值
     *
     * @param w
     * @param v
     * @param index
     * @param rest  剩余空间
     * @return
     */
    public static int process(int[] w, int[] v, int index, int rest) {

        // base case 1 ,剩余空间小于等于0，返回 -1
        if (rest <= 0) {
            return -1;
        }

        // base case 2 , 索引位置到w.length，没有货了，返回0
        // rest >=0
        if (index == w.length) {
            return 0;
        }

        // 有货也有空间
        // 情况一：没有要当前位置货，直接调用递归
        int p1 = process(w, v, index + 1, rest);
        int p2 = -1;
        // 情况一：要当前位置货，减去当前货的重量，再调用递归
        int p2Next = process(w, v, index + 1, rest - w[index]);
        if (p2Next != -1) {
            p2 = v[index] + p2Next;
        }
        // 情况一二比较，返回最大
        return Math.max(p1, p2);
    }



    /**
     * 动态规划 通过 maxValue 修改过来的
     *
     * @param w
     * @param v
     * @param bag
     * @return
     */
    public static int dpWay(int[] w, int[] v, int bag) {
        int N = w.length;
        // 声明二维数组，存储背包问题在不同情况下的值
        int[][] dp = new int[N + 1][bag + 1];
        // int[N][...] 初始化已经是0
        // 从下面的行，依次往上填
        for (int index = N - 1; index >= 0; index--) {
            // 从左往右填
            for (int rest = 1; rest <= bag; rest++) {

                int p1 = dp[index + 1][rest];
                int p2 = -1;
                if(rest - w[index]>=0){
                    p2= v[index] +dp[index + 1][rest - w[index]];
                }
                dp[index][rest] = Math.max(p1,p2);
            }
        }
        return dp[0][bag];
    }

    /**
     * 动态规划
     *
     * @param w
     * @param v
     * @param bag
     * @return
     */
    public static int dpWay1(int[] w, int[] v, int bag) {
        int N = w.length;
        int[][] dp = new int[N + 1][bag + 1];
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 1; rest <= bag; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest >= w[index]) {
                    dp[index][rest] = Math.max(dp[index][rest], v[index] + dp[index + 1][rest - w[index]]);
                }
            }
        }
        return dp[0][bag];
    }


}
